#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TRUE    1
#define FALSE   0
#define ERR_INPUT   -1

#define CHAR_NULL '\0'


int sub_str(char *s, char *t)
{
    if (s == NULL || t == NULL)
        return ERR_INPUT;

    /* 使用动态规划 */
    int i = 0;
    int j = 0;
    int str_len = strlen(t);
    int dp_arr[str_len + 1][26];
    memset(dp_arr, 0 , sizeof(dp_arr));
    for (i = 0; i < 26; i++)
        dp_arr[str_len][i] = str_len;
    for (i = str_len - 1; i >= 0; i--)
    {
        for (j = 0; j < 26; j++)
        {
            if (t[i] == j + 'a')
                dp_arr[i][j] = i;   /* 用一个二维数组，每一行的每一个数据储存的是后面的字母i的出现的位置 */
            else
                dp_arr[i][j] = dp_arr[i + 1][j];
        }
    }

    j = 0;
    for (i = 0; s[i] != CHAR_NULL; i++)
    {
        if (dp_arr[j][s[i] - 'a'] == str_len)
            return FALSE;
        else
            j = dp_arr[j][s[i] - 'a'] + 1;
    }
    return TRUE;
}

int main()
{
    char *s1 = "abcrt";
    char *s2 = "sakdhkgsammbkkcrrrrtt";
    int res = sub_str(s1, s2);
    if (res == TRUE)
        printf("Is sub str\n");
    else
        printf("Is not sub str\n");
    return 0;
}